#include <iostream>
#include "SortTestHelper.h"
#include "IndexMaxHeap.h"

using namespace std;

template<typename Item>
class IndexMaxHeapBeat {

private:
    Item *data;
    int *indexs;
    int *reverse;
    int count;
    int capacity;


    //k为索引值，indexs[k] 比较，交换索引
    void shiftUp(int k) {

        //获取该索引的值
        int idx = indexs[k];
        //获取该索引的元素值
        Item e = data[idx];

        //寻找索引的元素值的位置
        /**
         * 小于号写错地方了
         * data[indexs[k / 2]< e] 更正为 data[indexs[k / 2]] < e  ！！！！
         */
        while (k > 1 && data[indexs[k / 2]] < e) {

            //将indexs[k/2]索引和indexs[k]进行复制操作
            int j = k / 2;

            indexs[k] = indexs[j];
            reverse[indexs[k]] = k;
            k = j;
        }
        indexs[k] = idx;
        reverse[indexs[k]] = k;
    }

    void shiftDown(int k) {

        //优化点：将多次交换变为赋值后插入
        int idx = indexs[k];
        Item v = data[idx];

        while (2 * k <= count) {//判断数组有没有越界

            int j = 2 * k;      //在本次循环中，索引k与j的进行交换（默认左孩子）

            if (j + 1 <= count && data[indexs[j + 1]] > data[indexs[j]]) {  //寻找较大的孩子结点，
                j += 1;
            }

            if (v >= data[indexs[j]]) {   //待调整元素与将挑换元素大于相等就不赋值
                break;
            }

            indexs[k] = indexs[j];      //将替换元素数值赋值给父节点
            reverse[indexs[k]] = k;
            k = j;      //下一个待调整元素的索引
        }

        indexs[k] = idx;
        reverse[indexs[k]] = k;
    }

public:
    IndexMaxHeapBeat<Item>(int capacity) {
        data = new Item[capacity + 1];
        indexs = new int[capacity + 1];
        reverse = new int[capacity + 1];

        for (int i = 0; i <= capacity; ++i) {
            reverse[i] = 0;
        }

        count = 0;
        this->capacity = capacity;
    }

    ~IndexMaxHeapBeat() {
        delete[] data;
        delete[] indexs;
        delete[] reverse;
    }

    int size() {
        return count;
    }

    bool isEmpty() {
        return count == 0;
    }

    //i from 0
    void insert(int i, Item item) {

        assert(count + 1 <= capacity);
        assert(i + 1 >= 1 && i + 1 <= capacity);

        i += 1;
        data[i] = item;     //存储值
        indexs[count + 1] = i;    //存储索引index
        reverse[i] = count + 1;
        count++;

        shiftUp(count);
    }

    Item extractMax() {

        assert(count > 0);      //堆是否为空

        Item ret = data[indexs[1]];     //返回最大的值

        swap(data[indexs[1]], data[indexs[count]]); //交换最大的结点与最后一个结点；也可以将最后一个元素赋值给第一个元素
        reverse[indexs[1]] = 1;
        reverse[indexs[count]] = 0;

        count--;        //堆大小减1

        shiftDown(1);   //维护堆，将data[i]的元素调整到应该的位置

        return ret;
    }

    int extractMaxIndex() {

        assert(count > 0);      //堆是否为空

        int ret = indexs[1] - 1;     //返回最大的值

        swap(indexs[1], indexs[count]); //交换最大的结点与最后一个结点；也可以将最后一个元素赋值给第一个元素
        reverse[indexs[1]] = 1;
        reverse[indexs[count]] = 0;

        count--;        //堆大小减1

        shiftDown(1);   //维护堆，将data[i]的元素调整到应该的位置

        return ret;
    }

    //判断该data索引是否有值
    bool contains(int i) {

        //越界处理
        assert(i + 1 >= 1 && i + 1 < capacity);
        return reverse[i + 1] != 0;
    }

    Item getItem(int i) {

        assert(contains(i));
        return data[i + 1];
    }

    void change(int i, Item newItem) {

        assert(contains(i));
        //i 为data中的索引
        i += 1;
        data[i] = newItem;

        //维护堆
        //找到indexs[j] = i ,j表示data[i]在堆中的位置
        //在对索引j进行shiftUp(j),shiftDown(j)
//        for (int j = 1; j <= count; j++) {
//            //对比索引堆中的值和更改元素的索引
//            if (indexs[j] == i) {
//                shiftDown(j);
//                shiftUp(j);
//                return;
//            }
//        }

        int j = reverse[i];
        shiftDown(j);
        shiftUp(j);
    }
};

template<typename T>
void heapSortUsingIndexMaxHeap(T arr[], int n) {

    IndexMaxHeap<T> indexMaxHeap = IndexMaxHeap<T>(n);
    for (int i = 0; i < n; i++) {
        indexMaxHeap.insert(i, arr[i]);
    }

    for (int i = n - 1; i >= 0; i--) {

        arr[i] = indexMaxHeap.extractMax();
    }

}

template<typename T>
void heapSortUsingIndexMaxHeapBeat(T arr[], int n) {

    IndexMaxHeapBeat<T> indexMaxHeapBeat = IndexMaxHeapBeat<T>(n);
    for (int i = 0; i < n; i++) {
        indexMaxHeapBeat.insert(i, arr[i]);
    }

    for (int i = n - 1; i >= 0; i--) {

        arr[i] = indexMaxHeapBeat.extractMax();
    }

}

int main() {

    int n = 1000000;

    int *arr = SortTestHelper::generateRandomArray(n, 1, n);
    int *arr1 = SortTestHelper::generateRandomArray(n, 1, n);

    SortTestHelper::testSort("heapSort Using Index-Max-Heap", heapSortUsingIndexMaxHeap, arr, n);
    SortTestHelper::testSort("heapSort Using Index-Max-Heap-Beat", heapSortUsingIndexMaxHeapBeat, arr1, n);

    delete[] arr;
    delete[] arr1;
    cout << endl;

    return 0;
}